package com.example.algo;


class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        // 永远保证数组1 < 数组2
        if(nums1.length > nums2.length){
            return findMedianSortedArrays(nums2, nums1);
        }

        // 数组1的长度
        int m = nums1.length;
        // 数组2的长度
        int n = nums2.length;
        // 两个数组中元素个数总和
        int len = m + n;
        // 中位数左边所有元素个数，len + 1 当 len 为奇数时，左边会比右边多一个，当 len 为偶数时，左右个数相等
        int leftTotal = (len + 1) / 2;
        // left 和 right 作为每次循环第一个数组的左边界和右边界
        // 起始位置 左边为0  右边为第一个数组的长度
        int left = 0, right = m;
        // len 是奇数的时候，中位数是 median1
        // len 是偶数的时候，中位数是 (median1 + median2) / 2
        int median1 = 0, median2 = 0;

        // 左边的位置小于等于右边的位置表示还未找到目标位置，需要继续循环
        // 当left>right的时候就是查找到目标位置，就要结束循环
        while(left <= right) {
            // i、j 分别是第一、第二个数组中目标数据的下标，当 i 增加的时候 j 就会减少
            // left + (right - left) / 2 等于 (left + right) / 2，前者可以防止超出 integer 的容量
            int i = left + (right - left) / 2;
            // 分割线左边元素个数减去第一个数组的开始下标，剩下就是第二个数组要开始寻找的下标
            int j = leftTotal - i;

            int left_i_max = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
            int right_i_min = i == m ? Integer.MAX_VALUE : nums1[i];
            int left_j_max = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
            int right_j_min = j == n ? Integer.MAX_VALUE : nums2[j];

            // 当 nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i] 成立的时候
            // 表示 left 太向前了，需要向后移动，再次查找区间需要锁定在 [i, right]
            // 当条件不成立的时候，就是 rigth 取的太向后了，需要向前移动，再次查找区间需要锁定在[left, i-1]
            // 上面因为是 并且 关系，所以只要 nums1[i-1] > nums2[j] 的时候，就需要在 [left, i-1] 的区间查找
            if(left_i_max <= right_j_min){
                median1 = Math.max(left_i_max, left_j_max);
                median2 = Math.min(right_i_min, right_j_min);
                left = i + 1;
            } else {
                right = i - 1;
            }
        }
        return len % 2 == 1 ? median1 : (median1 + median2) / 2.0;
    }

}